//
// Created by Incredible on 17/3/23.
//

#ifndef GRAPHTHEORY_PATH_H
#define GRAPHTHEORY_PATH_H

#include<iostream>
#include <cassert>
#include <vector>
#include <stack>

using namespace std;

template<typename Graph>
class Path {

private:
    Graph G;        //待搜索图
    bool *visited;   //是否访问过
    int *from;     //前导节点
    int s;          //初始点

    //深度优先遍历
    void dfs(int s) {

        //TODO 维护访问数组和from数组
        visited[s] = true;

        //遍历源点的临接点
        typename Graph::adjIterator adjIterator(G, s);
        for (int i = adjIterator.begin(); !adjIterator.end(); i = adjIterator.next()) {

            if (!visited[i]) {

                //维护from数组
                from[i] = s;
                dfs(i);
            }
        }
    }

public:

//初始化
    Path(Graph G, int s) : G(G) {
        visited = new bool[G.V()];
        from = new int[G.V()];
        this->s = s;

        //初始化成员属性
        for (int i = 0; i < G.V(); ++i) {
            visited[i] = false;
            from[i] = -1;
        }

        //寻路
        for (int j = 0; j <G.V(); ++j) {
            if (!visited[j]) {
                dfs(j);
            }
        }

    }

    //TODO 可以做3件事：1. 是否有路；2. 路径内容 3.打印路径

    //是否有路:如果有路则在初始化时候：该节点被访问过
    bool hasPath(int v) {
        return visited[v];
    }

    //求解路径: 目标点依照from数组向上搜索，直到搜索到源节点
    void findPath(int v, vector<int> &vec) {

        //用栈保存路径，（倒序输出）
        stack<int> s;

        s.push(v);
        int p = v;

        while (p != -1) {
            s.push(p);
            p = from[p];
        }

        vec.clear();

        while (!s.empty()) {
            vec.push_back(s.top());
            s.pop();
        }
    }

    //打印路径
    void showPath(int v) {

        vector<int> vec;
        findPath(v, vec);

        for (int i = 0; i < vec.size(); ++i) {
            cout<<vec[i];
            if(i == vec.size() - 1){
                cout<<endl;
            } else{
                cout<<" --> ";
            }
        }
    }
};

#endif //GRAPHTHEORY_PATH_H
